package Hash;

import java.util.HashMap;

public class twoSum {
    // 方法一：双重循环——时间复杂度O(n^2)
    public static int[] twoSum1(int[] nums, int targer) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == targer) {
                    return new int[] { i, j };
                }
            }
        }
        return nums;
    }

    // 方法二：基于hash表的方法——时间复杂度O(n)
    public static int[] twoSum2(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == null && map.get(target - nums[i]) == null) {
                // key是值，value是索引
                map.put(nums[i], i);
            } else {
                if (map.get(target - nums[i]) != null) {
                    return new int[] { map.get(target - nums[i]), i };
                }
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[] { 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1 };
        int[] result = twoSum2(nums, 11);
        for (int r : result) {
            System.out.println(r);
        }
    }

}
